import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * <p>
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 * 说明：
 * <p>
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 */
class Solution {

    public static void main(String[] args) {
        List<List<String>> lists = groupAnagrams(new String[]{"tho", "tin", "erg", "end", "pug", "ton", "alb", "mes", "job", "ads", "soy", "toe", "tap", "sen", "ape", "led", "rig", "rig", "con", "wac", "gog", "zen", "hay", "lie", "pay", "kid", "oaf", "arc", "hay", "vet", "sat", "gap", "hop", "ben", "gem", "dem", "pie", "eco", "cub", "coy", "pep", "wot", "wee"});
        System.out.println(lists.size());
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }


    public static List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            byte[] bytes = new byte[26];
            for (int i = 0; i < str.length(); i++) {
                bytes[str.charAt(i) - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append("-").append(bytes[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }


    private static byte a = 80;
    private static byte b = 40;
    private static byte c = 20;
    private static byte d = 8;
    private static byte e = 4;
    private static byte f = 2;
    private static byte g = 1;

    /**
     * 字幕会重复，所以不能用这种方式
     *
     * @param bytes
     * @param character
     */
    private static void handle(byte[] bytes, char character) {
        switch (character) {
            case 'a':
                bytes[0] = (byte) (bytes[0] | a);
                break;
            case 'b':
                bytes[0] = (byte) (bytes[0] | b);
                break;
            case 'c':
                bytes[0] = (byte) (bytes[0] | c);
                break;
            case 'd':
                bytes[0] = (byte) (bytes[0] | d);
                break;
            case 'e':
                bytes[0] = (byte) (bytes[0] | e);
                break;
            case 'f':
                bytes[0] = (byte) (bytes[0] | f);
                break;
            case 'g':
                bytes[0] = (byte) (bytes[0] | g);
                break;
            case 'h':
                bytes[1] = (byte) (bytes[0] | a);
                break;
            case 'i':
                bytes[1] = (byte) (bytes[1] | b);
                break;
            case 'j':
                bytes[1] = (byte) (bytes[1] | c);
                break;
            case 'k':
                bytes[1] = (byte) (bytes[1] | d);
                break;
            case 'l':
                bytes[1] = (byte) (bytes[1] | e);
                break;
            case 'm':
                bytes[1] = (byte) (bytes[1] | f);
                break;
            case 'n':
                bytes[1] = (byte) (bytes[1] | g);
                break;
            case 'o':
                bytes[2] = (byte) (bytes[2] | a);
                break;
            case 'p':
                bytes[2] = (byte) (bytes[2] | b);
                break;
            case 'q':
                bytes[2] = (byte) (bytes[2] | c);
                break;
            case 'r':
                bytes[2] = (byte) (bytes[2] | d);
                break;
            case 's':
                bytes[2] = (byte) (bytes[2] | e);
                break;
            case 't':
                bytes[2] = (byte) (bytes[2] | f);
                break;
            case 'u':
                bytes[2] = (byte) (bytes[2] | g);
                break;
            case 'v':
                bytes[3] = (byte) (bytes[3] | a);
                break;
            case 'w':
                bytes[3] = (byte) (bytes[3] | b);
                break;
            case 'x':
                bytes[3] = (byte) (bytes[3] | c);
                break;
            case 'y':
                bytes[3] = (byte) (bytes[3] | e);
                break;
            case 'z':
                bytes[3] = (byte) (bytes[3] | f);
                break;
        }
    }

}